﻿#include"Stack.h"
void swap(int* x, int* y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

// 快速排序hoare版本(1)
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;

	int key = left++;

	while (left <= right)
	{
		while (left <= right && arr[right] > arr[key])
		{
			right--;
		}
		while (left <= right && arr[left] < arr[key])
		{
			left++;
		}

		if (left <= right)
		{
			swap(&arr[left++], &arr[right--]);
		}
	}
	swap(&arr[key], &arr[right]);

	quicksort(arr, begin, right - 1);
	quicksort(arr, right + 1, end);
}

// 快速排序hoare版本(2)
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;

	int key = left;

	while (left < right)
	{
		while (left < right && arr[right] > arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}

		swap(&arr[left], &arr[right]);
	}
	swap(&arr[key], &arr[right]);

	quicksort(arr, begin, right - 1);
	quicksort(arr, right + 1, end);
}

// 快速排序挖坑法
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;

	int hole = left;
	int key = arr[hole];

	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	quicksort(arr, begin, hole - 1);
	quicksort(arr, hole + 1,end);
}

// 快速排序前后指针法
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int prev = left;
	int cur = left + 1;

	while (cur <= right)
	{
		if (arr[cur] < arr[left])
		{
			prev++;
			swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	swap(&arr[prev], &arr[left]);

	quicksort(arr, left, prev-1);
	quicksort(arr, prev + 1, right);
}


// 快速排序 非递归实现(借用数据结构——栈)
void QuickSortNonR(int* arr, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);

		int prev = begin;
		int cur = begin + 1;
		while (cur <= end)
		{
			if (arr[cur] < arr[begin])
			{
				prev++;
				swap(&arr[prev], &arr[cur]);
			}
			cur++;
		}
		swap(&arr[prev], &arr[begin]);

		if (prev + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, prev + 1);
		}
		if (begin < prev - 1)
		{
			StackPush(&st, prev - 1);
			StackPush(&st, begin);
		}
	}

	StackDestroy(&st);
}
